10069 - Distinct subsequences/p10069.java

   1 /*
   2   Problema: 10069 - Distinct Subsequences
   3   Aceptado por el juez de la UVa
   4   Este código muestra tanto I/O como BigInteger
   5
   6   Autor: Andrés Mejía-Posada
   7  */
   8 import java.util.*;
   9 import java.io.*;
  10 import java.math.*;
  11
  12 class Main {
  13     public static void main(String[] args) throws IOException {
  14         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  15         String line = reader.readLine();
  16         StringTokenizer tokenizer = new StringTokenizer(line);
  17         int N = Integer.valueOf(tokenizer.nextToken());
  18         while (N-- > 0){
  19             String a, b;
  20             a = reader.readLine();
  21             b = reader.readLine();
  22
  23             int A = a.length(), B = b.length();
  24             if (B > A){
  25                 System.out.println("0");
  26             }else{
  27                 BigInteger dp[][] = new BigInteger[2][A];
  28                 /*
  29                   dp[i][j] = cantidad de maneras diferentes
  30                   en que puedo distribuir las primeras i
  31                   letras de la subsecuencia (b) terminando
  32                   en la letra j de la secuencia original (a)
  33                 */
  34
  35                 if (a.charAt(0) == b.charAt(0)){
  36                     dp[0][0] = BigInteger.ONE;
  37                 }else{
  38                     dp[0][0] = BigInteger.ZERO;
  39                 }
  40                 for (int j=1; j<A; ++j){
  41                     dp[0][j] = dp[0][j-1];
  42                     if (a.charAt(j) == b.charAt(0)){
  43                         dp[0][j] = dp[0][j].add(BigInteger.ONE);
  44                     }
  45                 }
  46
  47                 for (int i=1; i<B; ++i){
  48                     dp[i%2][0] = BigInteger.ZERO;
  49                     for (int j=1; j<A; ++j){
  50                         dp[i%2][j] = dp[i%2][j-1];
  51                         if (a.charAt(j) == b.charAt(i)){
  52                             dp[i%2][j] = dp[i%2][j].add(dp[(i+1)%2][j-1]);
  53                         }
  54                     }
  55                 }
  56                 System.out.println(dp[(B-1)%2][A-1].toString());
  57             }
  58         }
  59     }
  60 }